package nextoffer.bytedance;

import java.io.*;

public class TwoF {

    public static void main(String[] args) throws Exception {
        int n,k;
        PrintWriter p = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        Read in = new Read();
        n = in.nextInt();
        k = in.nextInt();
        String template = in.readLine();

        while(k-- >0){
            String tmp = in.readLine();
            int count = countPatternOccurrences(template, tmp);
            System.out.println(count);
            
        }
        // 47 46 45 44 43 42  40 88
    }
/**
 * 10 3
 bobobalice
 bob
 alice
 red
 */

    // 构建KMP部分匹配表
    private static int[] buildPartialMatchTable(String pattern) {
        int[] partialMatchTable = new int[pattern.length()];
        int length = 0; // 最长前缀后缀匹配长度

        for (int i = 1; i < pattern.length(); ) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                partialMatchTable[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = partialMatchTable[length - 1];
                } else {
                    partialMatchTable[i] = 0;
                    i++;
                }
            }
        }
        return partialMatchTable;
    }

    // 计算字符串B在字符串A中出现的次数
    private static int countPatternOccurrences(String text, String pattern) {
        int[] partialMatchTable = buildPartialMatchTable(pattern);
        int count = 0;
        int i = 0; // 指向文本的指针
        int j = 0; // 指向模式的指针

        while (i < text.length()) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }

            if (j == pattern.length()) {
                count++;
                j = partialMatchTable[j - 1];
            } else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = partialMatchTable[j - 1];
                } else {
                    i++;
                }
            }
        }

        return count;
    }
}
class Read{
    StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public int nextInt() throws Exception{
        st.nextToken();
        return (int)st.nval;
    }
    public String readLine() throws Exception{	//	这个不推荐使用
        st.nextToken();
        return st.sval;
    }
}
